\documentclass{article}
\usepackage{listings} % 用于插入代码
\usepackage{tikz} % 用于绘制图形
\usetikzlibrary{trees} % 用于绘制树状图

\usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\usepackage[UTF8]{ctex}
% Useful packages
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{listings}
% 设置 listings 宏包的参数
\lstset{
    language=C++, % 代码语言
    basicstyle=\ttfamily, % 基本字体风格
    keywordstyle=\bfseries, % 关键字风格
    commentstyle=\itshape, % 注释风格
    stringstyle=\ttfamily, % 字符串风格
    breaklines=true, % 自动换行
    columns=flexible, % 列的灵活性
    numbers=left, % 行号在左侧
    numberstyle=\tiny, % 行号字体大小
    frame=single, % 代码框
    showstringspaces=false % 不显示字符串中的空格
}



\title{样条实现大作业报告}
\author{3220100159 梁越}

\begin{document}
	\maketitle

\section*{一、代码结构}
\begin{tikzpicture}[level distance=1.5cm,
  level 1/.style={sibling distance=7.5cm},
  level 2/.style={sibling distance=3.5cm},
  level 3/.style={sibling distance=3.5cm}]
  
  \node {Polynomials.h}
    child { node {Spline.h}
      child { node {B\_basis\_function.h} % 修改了变量名的格式
        child { node {CubicBSplines.h} }
        child { node {QuadraticBSplines.h} }
        child { node {LinearBSplines.h} }
        child { node {BSplines.h} }
      }
      child { node {CubicPPSplines.h} }
      child { node {LinearPPSplines.h} } % 修正了拼写错误
    };
  
\end{tikzpicture}

\section*{二、详细介绍}
\subsection*{1.大概框架}
以下是主要的头文件的实现内容\\
$Polynomials.h$(用于生成pp样条的每段多项式)\\
Spline.h(B样条和PP样条的基本类定义)\\
B\_basis\_function.h(定义B样条的基函数，包括求值，求一阶导，二阶导)
LinearPPSpines.h(PP线性样条函数实现)\\
LinearBSplines.h(B线性样条函数实现)\\
QuadraticBSplines.h(二次B样条实现)\\
CubicBSplines.h ,CubicPPSplines.h(B样条和PP样条的三阶周期、自然、边界样条实现)\\
BSplines.h(在给定节点序列x,次数degree，系数a的条件下，实现了任意阶任意节点样条的绘制)\\
Curvefitting.cpp实现了平面上的样条曲线拟合（需要用户给出曲线，节点个数，区间，以及要生成的样类型，在完成E题时修改了部分内容，E.cpp不再需要用户输入，而是根据给定函数计算）
\subsection*{2.测试函数说明}
\\
BSplines\_test.cpp:
（实现了公式\(S(t) = \sum_{i=2-n}^{N} a_{i} B_{i}^{n}(t) \in S_{n}^{n-1}(t_{1}, \ldots, t_{n}), \quad t \in [t_{1}, t_{N}]\)）\\
\begin{lstlisting}
请输入节点个数：
5
请输入节点：
1 2 3 4 5
请输入样条的阶数：
3 
请输入系数：
1 2 1 2 1 2 1
曲线绘制完成，图像保存为 spline_curve.png

\end{lstlisting}
Curvefitting.cpp运行后 ，会要求用户输入需要拟合的函数以及对节点等的要求，从而绘制拟合的样条曲线并与
原曲线对比。目前实现的是三次样条拟合（三种PP样条，三种B样条）。\\
\begin{lstlisting}
请输入节点数量：
用户：15 
请输入节点区间（例如 0 和 10）:
用户：0 10
请输入函数表达式（变量用x，例如 sin(x) 或 x^2）：
用户：x^2
请选择样条拟合类型：
1. 完全B样条
2. 自然B样条
3. 周期B样条
4. 完全pp样条
5. 自然pp样条
6. 周期pp样条
用户：1
请输入边界条件 m_1 和 m_n（以空格分隔）：
用户：0 20
complete
Plot saved as 'curvefitting.png'

\end{lstlisting}

test.cpp运行后会生成六种样条关于sinx的拟合情况，可以更改函数，节点数量，区间等,主要用于测试B样条和PP样条，图片显示，两种样条在给定同样的条件时拟合的曲线完全一致，图片见Comparison of PP and B Splines.png
\subsection*{3.主要函数实现逻辑}
\subsubsection*{（1）B样条}
首先实现了基函数，然后利用矩阵计算出系数，最后实现B样条任意点求值。\\
主要用到的数学定理为讲义def3.23(基函数求值)\\
B-splines are defined recursively by
\begin{equation}
B_{i}^{n+1}(x) = \frac{x - t_{i-1}}{t_{i+n} - t_{i-1}} B_{i}^{n}(x) + \frac{t_{i+n+1} - x}{t_{i+n+1} - t_{i}} B_{i+1}^{n}(x). \tag{3.30}
\end{equation}

The recursion base is the B-spline of degree zero,
\begin{equation}
B_{i}^{0}(x) = 
\begin{cases} 
1 & \text{if } x \in (t_{i-1}, t_{i}], \\
0 & \text{otherwise.}
\end{cases} \tag{3.31}
\end{equation}
Thm3.34(求导)
\begin{equation}
\frac{\mathrm{d}}{\mathrm{d}x} B_{i}^{n}(x) = \frac{n B_{i}^{n-1}(x)}{t_{i+n-1} - t_{i-1}} - \frac{n B_{i+1}^{n-1}(x)}{t_{i+n} - t_{i}}.
\end{equation}
\begin{lstlisting}

class B_Basis_function {
public:
    int degree;
    int index;
    std::vector<double> knots;

    // 构造函数
    B_Basis_function() {}
    B_Basis_function(int degree, int index, std::vector<double> knots);

    //递归求值函数，公式来源讲义Definition3.23
    double value(double x);
    //递归求一阶导，公式Theorem3.34
    double m(double x_value);
    //递归求二阶导，基本逻辑与一阶导相同
    double M(double x_value);
    //在给的节点两端补点，以正确计算索引小于0或大于n的基函数
    int checkIndex(int index);
};
\end{lstlisting}
CubicBSplines和QuadraticBSplines分别继承了BSplines，实现了三种三次样条（完全、自然、周期），以及二次样条）（Theorem3.58）,包括矩阵求解B样条系数函数和B样条求值函数。\\
基于基函数的矩阵计算系数函数\\
\begin{lstlisting}
    //三次样条，每个区间上都受到三个函数的影响
    for(int i = 1; i <= n; i++){
        for(int j = i-1; j <= i+1; j++){
            B_Basis_function B(3, j-2, knots);
            A(i, j) = B.value(knots[i-1]);
        }
        b[i] = f[i-1];
    }
    //边界条件 ：边界节点的一阶导设置
    
    a=A.colPivHouseholderQr().solve(b);
    //a即为所求系数，存入以供求值使用
\end{lstlisting}
求值函数，通过求解每一个基函数在给定x处的值，结合系数计算B样条的值。\\
\\
\begin{lstlisting}
        for(int i=0;i<n+2;i++){
            B_Basis_function B(3,i-2,knots);
            result += coefficients[i]*B.value(x_value);
        }
        return result;
}
\end{lstlisting}
其余两种样条函数以及二阶B样条思路基本一致，只有边界条件限制和阶数不同，略去详细介绍。

\subsubsection*{（2）PP样条}
首先介绍多项式类：
\begin{lstlisting}
class Polynomial {
public:
    double left_point;\\左端点
    double right_point;\\右端点
    int degree;\\多项式次数
    vector<double> coefficients;\\多项式系数，从低次开始

public:
    // 在给定点 x 处计算多项式的值
    double value(double x) const；
};
\end{lstlisting}
PP样条在每一段上都是多项式，所以首先建立多项式类，以搭建基本框架，再建立矩阵计算每个多项式的系数，从而求值。
多项式类主要包含左端点，右端点，系数向量和多项式次数这几个成员。
\begin{lstlisting}
    for (int i = 0; i <= degree; i++) {
            result += coefficients[i] * pow(x - left_point, i);
        }
\end{lstlisting}
求解系数
\begin{lstlisting} 
    Eigen::MatrixXd A=Eigen::MatrixXd::Zero(n,n);
    Eigen::VectorXd b=Eigen::VectorXd::Zero(n);
    //计算m矩阵
    m_A = A.colPivHouseholderQr().solve(b);
}
\end{lstlisting}
\[\lambda_i m_i + 2m_i + \mu_i m_{i+1} = 3\mu_i f[x_i, x_{i+1}] + 3\lambda_i f[x_{i-1}, x_i]\]
\[lamda_i=\frac{x[i+1]-x[i]}{x[i+1]-x[i-1]},mu_i=\frac{x[i]-x[i-1]}{x[i+1]-x[i-1]}\]
矩阵A如下：
\[
A = \begin{pmatrix}
1 & 0 & 0 & \cdots & 0 \\
\lambda_0 & 2 & \mu_0 & \cdots & 0 \\
0 & \lambda_1 & 2 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1
\end{pmatrix}
\]
b:
\[
b = \begin{pmatrix}
m_1 \\
 3\mu_0 \frac{f_2 - f_1}{x_2 - x_1} + 3\lambda_0 \frac{f_2 - f_1}{x_2 - x_1} - \lambda_0 m_1 \\
3\mu_{1} \frac{f_{3} - f_2}{x_{3} - x_2} + 3\lambda_{1} \frac{f_2 - f_{1}}{x_2 - x_{1}}\\
\vdots \\
3\mu_{n-3} \frac{f_{n-1} - f_{n-2}}{x_{n-1} - x_{n-2}} + 3\lambda_{n-3} \frac{f_{n-1} - f_{n-2}}{x_n - x_{n-1}} - \mu_{n-3} m_n \\
m_n
\end{pmatrix}
\]
其余两种只有边界条件不同，基本逻辑相同，略去详细介绍。
\\
\section*{三、项目作业完成情况}
\begin{enumerate}
    \item 在ppForm和BSpline格式下分别实现了线性样条函数$S_1^0$(LinearPPSplines.h,LinearBSplines.h)。
    \item 在ppForm格式下分别推导并实现了如下三类任意节点三次样条函数$S$：周期边界条件，自然样条，完全三次样条(CubicPPSplines.h)
    \item 在BSpline格式下分别推导并实现了如下三类任意节点三次样条函数$S$：周期边界条件，自然样条，完全三次样条(CubicBSplines.h)
    \item 验证ppForm和BSpline格式下取相同插值点和相同边界条件，得到的曲线是相同的(test.cpp)
    \item BSpline格式支持任意阶、任意节点样条的绘制。实现了公式
    \[
    S(t) = \sum_{i=2-n}^{N} a_i B_i^n(t) \in S_{n-1}^n(t_1, \ldots, t_n), t \in [t_1, t_N]
    \]
    给定节点序列$t_1, \ldots, t_n$、次数$n$、系数$a_i$，计算曲线$S(t)$(BSlines,h)
    \item 实现平面上的样条曲线拟合（Curvefitting.cpp）
\end{enumerate}
使用以上实现的内容完成了第三章全部编程习题。
\end{document}
